from typing import List 
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows=len(grid)#获取行数
        cols=len(grid[0])#获取列数
        cheery={}#三维数组用于缓存数据

        def dp(i:int,j:int,k:int)->int:
            if i>rows-1 or j<0 or k<0 or k>cols-1:#边界条件，不符合直接past掉
                return 0
            
            if (i,j,k)in cheery:#防止数据重复计算，优化
                return cheery[(i,j,k)]
            if j==k:#在同一个格子的时候，樱桃只获取一份
                current=grid[i][j]
            elif j!=k:#其余情况分别获取
                current=grid[i][j]+grid[i][k]

            max_cheery=0
            for j_change in (-1,0,1):#机器人1的选择
                for k_change in(-1,0,1):#机器人2的选择
                    j_next=j+j_change#最终情况
                    k_next=k+k_change
                    if 0<=j_next<cols and 0<=k_next<cols :#边界条件判定，机器人不能出格子
                        max_cheery=max(max_cheery,dp(i+1,j_next,k_next))#几种情况对比得出最多的樱桃数
                
            result=current+max_cheery#之前获取的加上下一步得到最多的樱桃数
            cheery[(i,j,k)]=result#数据存入数组

            return result
        return dp(0,0,cols-1)#直接递归

